//
//  333_最大二叉搜索子树.swift
//  Swift-LeetCode
//
//  Created by 卢悦明 on 2024/3/13.
/**
 给你一棵树，如果获取这个树最大的二叉搜索树的节点个数、
 */

import UIKit

/// 会员题
class GetMaxBST: NSObject {

    
    func getMaxBSTSubTree(_ root: TreeNode<Int>?) -> Int {
        guard let root = root else {
            return 0
        }
        if isBST(root) {
            return getNodeCount(root)
        }
        return max(getMaxBSTSubTree(root.left), getMaxBSTSubTree(root.right))
    }
    
    private func isBST(_ node: TreeNode<Int>?) -> Bool {
        
        return isNodeBST(node, minNum: Int.min, maxNum: Int.max)
    }
    
    private func isNodeBST(_ node: TreeNode<Int>?, minNum: Int, maxNum: Int) -> Bool {
        guard let node = node else {
            return true
        }
        if node.val <= minNum || node.val >= maxNum {
            return false
        }
        // 左边的节点都小于自己，右边的都大于自己
        return isNodeBST(node.left, minNum: minNum, maxNum: node.val) && isNodeBST(node.right, minNum: node.val, maxNum: maxNum)
    }
    
    private func getNodeCount(_ node: TreeNode<Int>?) -> Int {
        guard let node = node else {
            return 0
        }
        var queue = [TreeNode<Int>]()
        var count = 0
        queue.append(node)
        while !queue.isEmpty {
            let node = queue.removeFirst()
            count += 1
            if let left = node.left {
                queue.append(left)
            }
            if let right = node.right {
                queue.append(right)
            }
        }
        return count
    }
    

}
